package LearnAlgorithm.j_动态规划and贪心算法;

import java.util.Scanner;

/*
input:
7
2 -4 3 -1 2 -4 3
output:
4
 */
public class k最大子段和byDP {
	public static void main(String[] args) {
		k最大子段和byDP test = new k最大子段和byDP();
		test.useSumDP();
	}
	
	public void useSumDP() {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		int[] a = new int[N + 1];
		int[] dp = new int[N + 1];
		for (int i = 1; i < N + 1; i++) {
			a[i] = scanner.nextInt();
		}
		int ans = SumDP(a, dp, N);
		System.out.println(ans);
	}
	
	public int SumDP(int[] a, int[] dp, int N) {
		int ans = a[1];
		dp[1] = a[1];
		for (int i = 2; i <= N; i++) {
			dp[i] = dp[i - 1] > 0 ? dp[i - 1] + a[i] : a[i];
			ans = Math.max(ans, dp[i]);
		}
		return ans;
	}
}
